package fundamentals.unionfind;

import algUtils.StopWatch;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class UnionQuickFind {

    private int[] id;//分量id(以触点作为索引)
    private int count;//分量数量

    //
    /**
     * 初始化N个结点
     * @param N
     */
    public UnionQuickFind(int N){
        count=N;
        id=new int[N];
        for (int i = 0; i < N; i++) {
            id[i]=i;
        }
    }

    /**
     * 在p和q之间添加一条连接
     * @param p
     * @param q
     */
    public void union(int p,int q){
        int pID=id[p];
        int qID=id[q];
        if(pID==qID)return;
        for (int i = 0; i < id.length; i++) {
            if(id[i]==pID)id[i]=qID;
        }
        count--;
    }

    /**
     * p所在分量的标识符
     * @param p
     * @return
     */
    public int find(int p){
        return id[p];
    }

    /**
     * 如果p和q在同一个分量中，则返回true
     * @param p
     * @param q
     * @return
     */
    public boolean connected(int p,int q){

        return find(p)==find(q);
    }

    public int getCount(){
        return count;
    }

    public static void use(){
        int N = StdIn.readInt();
        UnionQuickFind uf = new UnionQuickFind(N);
        //QuickUnionFind uf=new QuickUnionFind(N);
        while (!StdIn.isEmpty()) {
            //读取整数对
            int p = StdIn.readInt();
            int q = StdIn.readInt();
            if (uf.connected(p, q)) continue;
            uf.union(p, q);
            StdOut.println(p + " " + q);
        }
    }

}
